# -*- coding: utf-8 -*-

''' Autor: Neuza Figueira - n.º 6036 '''

from random import uniform
from time import clock
import math
import matplotlib.pyplot as plt

class ShellSort():
    ''' Class to handle Shell sort implementation and testing.'''
    
    def shell_sort(self, A):
        '''Python Implementation of Shell sort.'''
        '''@param A -> List to sort.'''
        n = len(A) // 2
        while n > 0:
            for i, j in enumerate(A):
                while i >= n and A[i - n] > j:
                    A[i] = A[i - n]
                    i = i - n
                A[i] = j
                
            n = int(n/2)

        return A


    def testShellSort(self):
            '''Testing the complexity of Shell sort.'''
            Z = range(50, 1050, 50)
            T = []
            M = 50
            for n in Z:
                A = [ uniform(0.0, 1.0) for k in xrange(n)]
                tempos = []
                for k in range(M):
                    t1 = clock()
                    self.shell_sort(A)
                    t2 = clock()
                    tempos.append(t2-t1)
                media = reduce(lambda x, y: x + y, tempos) / len(tempos)
                var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
                
                T.append((n,media, var))

            X = [n for n, media, var in T]
            Y = [media for n, media, var in T]
            ct = 30e5 
            Z = [(n * (math.log(n, 2))) / ct  for n, media, var in T]


            plt.grid(True)
            plt.ylabel(u'T(n) - tempo de execução médio em segundos')
            plt.xlabel(u'n - número de elementos')
            plt.plot(X,Y,'rs', label="resultado experimental")
            plt.plot(X, Z, 'b^', label=u"previsão teórica")
            plt.legend()
            plt.show()
            pass
